package com.zwy.linear.impl;

import com.zwy.linear.LinearList;
import com.zwy.linear.SLNode;
import com.zwy.linear.Strategy;

/*
    单链表实现类
 */
public class ListSLinked implements LinearList {

    private Strategy strategy;//数据元素比较策略
    private SLNode head;   //单链表的首节点引用
    private int size;     //元素个数


    /**
     * 初始化数据
     * @param strategy
     */
    public ListSLinked(Strategy strategy) {
        this.strategy = strategy;
        head=new SLNode();
        size=0;
    }
    //辅助方法，获得数据元素e所在节点的前驱节点
    private SLNode getPreNode(Object e){
        SLNode p=head;
        while(p.getNext()!=null){
            if(strategy.equal(p.getNext().getData(),e)){
                return p;
            }
            else{
                p=p.getNext();
            }
        }
        return null;
    }
    //辅助方法：获取序号为0<=i<size的元素所在节点的前驱节点
    private SLNode getPreNode(int i){
        SLNode p=head;
        for (;i>0;i--){
            p=p.getNext();
        }
        return p;
    }
    //获得序号为0<=i<size的元素所在节点
    private SLNode getNode(int i){
        SLNode p=head.getNext();
        for (;i>0;i--){
            p=p.getNext();
        }
        return p;
    }

    @Override
    public int getSize() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size==0;
    }

    @Override
    public boolean contains(Object e) {
        SLNode p=head.getNext();
        while(p!=null){
            if(strategy.equal(p.getData(),e))return true;
            else p=p.getNext();
        }
        return false;
    }

    @Override
    public int indexOf(Object e) {
        SLNode p=head.getNext();
        int index=0;
        while(p!=null){
            if(strategy.equal(p.getData(),e))return index;
            else{
                index++;
                p=p.getNext();
            }
        }
        return -1;
    }

    @Override
    public void insert(int i, Object e) throws IndexOutOfBoundsException {
        if(i<0||i>size){
            throw new IndexOutOfBoundsException("序号越界");
        }
        SLNode p=getPreNode(i);
        SLNode q=new SLNode(e,p.getNext());
        p.setNext(q);
        size++;
        return;
    }

    @Override
    public boolean insertBefore(Object obj, Object e) {
        SLNode p=getPreNode(obj);
        if(p!=null){
            SLNode q=new SLNode(e,p.getNext());
            p.setNext(q);
            size++;
            return  true;
        }
        return false;
    }

    @Override
    public boolean insertAfter(Object obj, Object e) {
        SLNode p=head.getNext();
        while(p!=null){
            if(strategy.equal(p.getData(),obj)){
                SLNode q=new SLNode(e,p.getNext());
                p.setNext(q);
                size++;
                return true;
            }else{
                p=p.getNext();
            }
        }
        return false;
    }

    @Override
    public Object remove(int i) throws IndexOutOfBoundsException {
        if(i<0||i>size){
            throw new IndexOutOfBoundsException("序号越界");
        }
        SLNode p=getPreNode(i);
        Object obj=p.getNext().getData();
        p.setNext(p.getNext().getNext());
        size--;
        return obj;
    }

    @Override
    public boolean remove(Object e) {
        SLNode p=getPreNode(e);
        if(p!=null){
            p.setNext(p.getNext().getNext());
            size--;
            return true;
        }
        return false;
    }

    @Override
    public Object replace(int i, Object e) throws IndexOutOfBoundsException {
        if(i<0||i>size){
            throw new IndexOutOfBoundsException("序号越界");
        }
        SLNode p=getNode(i);
        Object obj=p.getData();
        p.setData(e);
        return obj;
    }

    @Override
    public Object get(int i) throws IndexOutOfBoundsException {
        if(i<0||i>size){
            throw new IndexOutOfBoundsException("序号越界");
        }
        SLNode p=getNode(i);
        return p.getData();
    }
}
